// 力扣148. 排序链表
// https://leetcode.cn/problems/sort-list/
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

// 打印链表
func (this *ListNode) Print() {
	cur := this
	format := ""
	for nil != cur {
		format += fmt.Sprintf("%+v", cur.Val)
		cur = cur.Next
		if nil != cur {
			format += "->"
		}
	}
	fmt.Println(format)
}

// 递归到只有一个数字的时候返回，然后再合并
func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	mid := findMiddle(head)

	tail := mid.Next
	mid.Next = nil

	left := sortList(head)
	right := sortList(tail)

	return mergeTwoLists(left, right)
}

// 快慢指针找链表的中点
func findMiddle(head *ListNode) *ListNode {
	slow := head
	fast := head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

// 力扣21.合并两个有序链表
// https://leetcode.cn/problems/merge-two-sorted-lists/
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	dummy := new(ListNode)
	cur := dummy
	// 遍历两个链表，每次比较链表头的大小，每次让较小值添加到 dummy 的后面，并且让较小值所在的链表后移一位
	for {
		if l1 == nil && l2 == nil {
			break
		}
		if l1 == nil {
			cur.Next = l2
			break
		}
		if l2 == nil {
			cur.Next = l1
			break
		}
		// 会出现一条链表遍历完，另外一条链表没遍历完的情况，需要将没遍历的链表添加到结果链表中
		if l1.Val < l2.Val {
			cur.Next = l1
			l1 = l1.Next
			cur = cur.Next
		} else {
			cur.Next = l2
			l2 = l2.Next
			cur = cur.Next
		}
	}
	return dummy.Next
}

func main() {
	list := &ListNode{
		Val: -1, Next: &ListNode{
			Val: 5, Next: &ListNode{
				Val: 3, Next: &ListNode{
					Val: 4, Next: &ListNode{
						Val: 0,
					},
				},
			},
		},
	}
	list.Print()           //-1->5->3->4->0
	sortList(list).Print() //-1->0->3->4->5
}
